import java.util.Arrays;

public class Test {
    public static void main(String[] args) {
        int[]nums = {1,9,2,8,37,4,6,5};
        heapSort(nums);
        //mergeSort(nums,0,nums.length-1);
        System.out.println(Arrays.toString(nums));
    }

    private static void heapSort(int[] nums) {
        for (int parent =(nums.length-1-1)/2 ; parent >=0 ; parent--) {
            siftDown(nums,parent,nums.length);
        }
        int end = nums.length-1;
        while(end>0){
            swap(nums,0,end);
            siftDown(nums,0,end);
            end--;
        }
    }

    private static void swap(int[] nums, int a, int b) {
        int tmp = nums[a];
        nums[a] = nums[b];
        nums[b] = tmp;
    }

    private static void siftDown(int[] nums, int parent, int n) {
        int child = parent*2+1;
        while (child<n){
            if(child+1<n&&nums[child+1]>nums[child]){
                child++;
            }
            if(nums[parent]<nums[child]){
                swap(nums,parent,child);
                parent = child;
                child = parent*2+1;
            }else{
                break;
            }
        }
    }

    private static void mergeSort(int[] nums, int left, int right) {
       if(left>=right)
            return;
       int mid = left+(right-left)/2;
       mergeSort(nums,left,mid);
       mergeSort(nums,mid+1,right);
       int[]tmp = new int[nums.length];
       int cur1 = left,cur2 = mid+1;
       int i = 0;
       while(cur1<=mid&&cur2<=right){
           tmp[i++] = nums[cur1]<nums[cur2]?nums[cur1++] : nums[cur2++];
       }
        while(cur1<=mid){
            tmp[i++] = nums[cur1++];
        }
        while(cur2<=right){
            tmp[i++] =  nums[cur2++];
        }
        for (int j = left; j <=right ; j++) {
            nums[j] = tmp[j-left];
        }
    }
}